/**
 * 376. 摆动序列
 * https://leetcode-cn.com/problems/wiggle-subsequence/
 */
public class Solutions_376 {
    public static void main(String[] args) {
//        int[] nums = {1, 7, 4, 9, 2, 5};  // output: 6
//        int[] nums = {1, 17, 5, 10, 13, 15, 10, 5, 16, 8};  // output: 7
        int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};  // output: 2
//        int[] nums = {};  // output: 0
//        int[] nums = {0, 0};  // output: 1
//        int[] nums = {84};  // output: 1
//        int[] nums = {3, 3, 3, 2, 5};  // output: 3

        int result = wiggleMaxLength(nums);
        System.out.println(result);
    }

    public static int wiggleMaxLength(int[] nums) {
        if (nums == null || nums.length < 2) {
            return nums.length;
        }
        // 之前记录的两个元素的差值
        int prevDiff = nums[1] - nums[0];
        int res = prevDiff == 0 ? 1 : 2;
        for (int i = 2; i < nums.length; i++) {
            // 当前两个元素的差值
            int curDiff = nums[i] - nums[i - 1];
            if (curDiff > 0 && prevDiff <= 0) {
                // 可以组成摆动序列
                res ++;
                prevDiff = curDiff;
            } else if (curDiff < 0 && prevDiff >= 0) {
                // 可以组成摆动序列
                res ++;
                prevDiff = curDiff;
            }
        }
        return res;
    }
}
